class unionset
{
public:
    vector<int> fa;
    unionset(int n)
    {
        for (int i = 0; i <= n; i++) fa.push_back(i);
    }
    int find(int n)
    {
        return fa[n] == n ? n : fa[n] = find(fa[n]);
    }
    void merge(int a, int b)
    {
        fa[find(a)] = find(b);
    }
};

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int n = grid.size(), m = grid[0].size();
        unionset s(305 * 305);
        for (int i = 0; i < grid.size(); i++)
        {
            for (int j = 0; j < grid[i].size(); j++)
            {
                if (grid[i][j] == '1')
                {
                    if (i + 1 < grid.size() && grid[i + 1][j] == '1') s.merge(i * n + j, (i + 1) * n + j);
                    if (j + 1 < grid[i].size() && grid[i][j + 1] == '1') s.merge(i * n + j, i * n + j + 1);
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < grid.size(); i++)
        {
            for (int j = 0; j < grid[i].size(); j++)
            {
                if (grid[i][j] == '1' && s.find(i * n + j) == i * n + j)
                {
                    ans += 1;
                }
            }
        }
        return ans;
    }
};